package com.hc.programming.array;

import com.hc.programming.util.ArrayUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 56.以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 * <p>
 * 示例 1：
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2：
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 * <p>
 * 提示：
 * 1 <= intervals.length <= 10^4
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 10^4
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/7/11 16:46
 */
public class 合并区间 {
    public static void main(String[] args) {
//        int[][] intervals = new int[][]{{8, 10}, {1,4}, {1, 3}, {2, 6}, {15, 18}};
//        Arrays.sort(intervals, (a1, a2)-> a1[0] == a2[0] ? a1[1] - a2[1] : a1[0] - a2[0]);
//        ArrayUtil.println(intervals);
        ArrayUtil.println(merge(new int[][]{{1, 4}, {4, 5}}));
        ArrayUtil.println(merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}}));
        ArrayUtil.println(merge(new int[][]{{1, 4}, {2, 3}}));
    }

    /**
     * 方案二：映射数组
     */
    public static int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        int max = 0, sum = 0, index = -1;
        for (int i[] : intervals) if (i[1] > max) max = i[1];
        int[] nums = new int[2 * max + 2];
        for (int i[] : intervals) {
            nums[2 * i[0]]++;
            nums[2 * i[1] + 1]--;
        }
        for (int i = 0; i < 2 * max + 2; i++) {
            sum += nums[i];
            if (sum != 0 && index == -1) {
                index = i;
            }
            if (sum == 0 && index != -1) {
                list.add(new int[]{index / 2, i / 2});
                index = -1;
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    /**
     * 方案一：排序 + 比较
     */
    public static int[][] merge2(int[][] intervals) {
        if (intervals.length == 0) {
            return intervals;
        }
        Arrays.sort(intervals, (a1, a2) -> a1[0] == a2[0] ? a1[1] - a2[1] : a1[0] - a2[0]);
        int[][] result = new int[intervals.length][2];
        int validLastIdx = 0;
        result[validLastIdx] = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (result[validLastIdx][1] < intervals[i][0]) {
                result[++validLastIdx] = intervals[i];
            } else if (result[validLastIdx][1] >= intervals[i][0] && result[validLastIdx][1] < intervals[i][1]) {
                result[validLastIdx][1] = intervals[i][1];
            }
        }
        if (result.length == validLastIdx + 1) {
            return result;
        }
        return Arrays.copyOf(result, validLastIdx + 1);
    }
}
